import java.util.Scanner;


/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-09-07
 * Time: 22:46
 */
public class Solution {

    /**
     * 二分
     */
    public int findNthDigit(int n) {
        int low = 1, high = 9;
        // 先算出最终 n 所在数字的位数
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (totalDigits(mid) < n) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        int d = low;
        // 前面 <= d 位的数组所占的位数总和
        int prevDigits = totalDigits(d - 1);
        // d 位数字总共占了多少位
        int index = n - prevDigits - 1;
        // d 位数字从哪开始
        int start = (int) Math.pow(10, d - 1);
        // n 在哪个数字上
        int num = start + index / d;
        // n 在哪个数字的哪一位上
        int digitIndex = index % d;
        int digit = (num / (int) (Math.pow(10, d - digitIndex - 1))) % 10;
        return digit;
    }

    /**
     *  计算这个位数的数字及 <= 这个位数的数字 总共所占的位数
     * @param length
     * @return
     */
    public int totalDigits(int length) {
        int digits = 0;
        int curLength = 1, curCount = 9;
        while (curLength <= length) {
            digits += curLength * curCount;
            curLength++;
            curCount *= 10;
        }
        return digits;
    }
}
